#pragma once

#include <list>

#include <boost/iterator.hpp>
#include <boost/noncopyable.hpp>
#include <boost/functional/hash.hpp>
#include <boostext/exception.hpp>
#include <boostext/container/list.hpp>
#include <boostext/util/verify.hpp>

#include "size2.hpp"
#include "vector2.hpp"
#include "rect.hpp"

// This define controls which list implementation should be used
// The quadtree uses boostext::list by default, which has a smaller
// memory footprint, than the list implementation from microsoft
//#define USE_STD_LIST

// This define controls if a quadtree should store some information
// in a per-instance storage, instead of per bucket
#define STORE_INSTANCE

// This define controls if the iterator calculates the rectangle during
// iteration or if the rectangle is calculated by the quadtree itself
#define ITERATOR_RECT




namespace math
{
	/**
	 * This is an optional base class for any filter class.
	 * A custom filter may inherit from this class in order to
	 * gain all necessary typedefs for all iterators of the quadtree.
	 * In order to implement the actual filtering function, it is necessary
	 * to provide an operator(), that takes the current iterator as the only
	 * argument and returns true if a bucket passed the test, and false if it didn't.
	 * Filtering is applied in a way, so that when a bucket doesn't pass the test,
	 * the tree assumes that neither of his children does, and simply moves on
	 * to the next sibling, instead of going further down in the tree.
	 *
	 * @usage
	 * struct my_filter : public base_filter< my_filter, quadtree<string, double> > {};
	 * my_filter filter;
	 * my_filter::iterator i = tree.begin(filter);
	 * my_filter::iterator end = tree.end(filter);
	 * while(i != end)
	 * {
	 *     ++i;
	 * }
	 */
	template <typename final_class, typename quadtree>
	struct base_filter
	{
	public:

		// Typedefs for the value type and const/ref variants
		typedef typename quadtree::value_type                                           value_type;
		typedef typename quadtree::ref_type                                             ref_type;
		typedef typename quadtree::const_value_type                                     const_value_type;
		typedef typename quadtree::const_ref_type                                       const_ref_type;

		// Typedefs for the flat_iterator (const & non-const)
		typedef typename quadtree::flat_iterator                                        flat_iterator;
		typedef typename quadtree::const_flat_iterator                                  const_flat_iterator;

		// Typedefs for the bucket_iterator (const & non-const)
		typedef typename quadtree::basic_bucket_iterator<quadtree, final_class>         bucket_iterator;
		typedef typename quadtree::basic_bucket_iterator<const quadtree, final_class>   const_bucket_iterator;

		// Typedefs for the deep_iterator (const & non-const)
		typedef typename quadtree::basic_value_iterator<bucket_iterator, flat_iterator, value_type>                     iterator;
		typedef typename quadtree::basic_value_iterator<const_bucket_iterator, const_flat_iterator, const_value_type>   const_iterator;
	};
	///////////////////////////////////////////////////////////////////////////////////////////////

	/**
	 * This class is an adapter class for those types that do not store
	 * their bounding rectangle. When one wants to store predefined types like
	 * a string, numbers, etc... then this is the class can be used to store those
	 * types in the quadtree.
	 * It is necessary to limit the amount of memory overhead, when the stored
	 * item is required to know it's rectangle anyway (whatever the reason might be).
	 * Otherwise there's a waisted 32 bytes per value, when using double precision.
	 *
	 * There is still memory overhead when one wants to store points only, but this cannot
	 * be prevented (at least I don't know of any way), without sacrificing speed.
	 */
	template <typename T, typename float_t, typename S = void>
	class quadtree_adaptor
		: boost::equality_comparable< quadtree_adaptor<T, float_t, S> >
	{
	public:

		typedef vector2<float_t, S>                            vector_type;
		typedef rectangle<float_t, S>                          rect_type;

		typedef typename boost::add_reference<T>::type         ref_T;
		typedef typename boost::add_const<T>::type             const_T;
		typedef typename boost::add_reference<const_T>::type   const_ref_T;

	public:

		const rect_type   m_rect;
		T                 m_value;

	public:

		/**
		 * Create a new default adaptor.
		 */
		quadtree_adaptor()
		{}

		/**
		 * Creates a new adaptor with the given rectangle and value.
		 */
		quadtree_adaptor(rect_type rect, const_ref_T value)
			: m_rect(rect)
			, m_value(value)
		{}



		/**
		 * Returns the bounding rectangle of this adaptor.
		 */
		rect_type boundingRect() const
		{
			return m_rect;
		}

		/**
		 * Returns the value of this adaptor.
		 */
		const_T value()
		{
			return m_value;
		}

		/**
		 * Returns the value of this adaptor.
		 */
		const_ref_T value() const
		{
			return m_value;
		}


		/**
		 * Converts this adaptor to the value type.
		 */
		operator ref_T()
		{
			return m_value;
		}

		/**
		 * Converts this adaptor to the value type.
		 */
		operator const_ref_T() const
		{
			return m_value;
		}

		/**
		 * Compares this adaptor against the other one.
		 */
		bool operator==(const quadtree_adaptor<T, float_t, S>& that) const
		{
			return m_rect == that.m_rect && m_value == that.m_value;
		}

		/**
		 * Compares this adaptor against the other one.
		 */
		bool operator<(const quadtree_adaptor<T, float_t, S>& that) const
		{
			if(m_rect < that.m_rect)
				return true;

			if(m_value < that.m_value)
				return true;

			return false;
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////

	template <typename T, typename float_t, typename S>
	vector2<float_t, S> position(const quadtree_adaptor<T, float_t, S>& that)
	{
		return that.boundingRect().center();
	}
	///////////////////////////////////////////////////////////////////////////////////////////////

	template <typename T, typename float_t, typename S>
	rectangle<float_t, S> boundingRect(const quadtree_adaptor<T, float_t, S>& that)
	{
		return that.boundingRect();
	}
	///////////////////////////////////////////////////////////////////////////////////////////////

	template <typename T, typename float_t, typename S>
	std::size_t hash_value(const quadtree_adaptor<T, float_t, S>& that)
	{
		std::size_t seed = 0;
		boost::hash_combine(seed, that.boundingRect());
		boost::hash_combine(seed, that.value());
		return seed;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////

	/**
	 * The quadtree models a tree that subdivides a 2-dimensional space
	 * into quads, each measuring a fourth the parent quad. Values are inserted
	 * based on their position in that space and the tree will subdivide itself
	 * once the number of values in one bucket reaches a certain threshold.
	 */
	template
	<
		typename T,
		typename float_type,
		typename S = void,
		typename value_storage = T //< Usually, the default parameter is just fine, but for objects that don't store their geometry, you must use the adaptor above
	>
	class quadtree
		: public boost::noncopyable
	{
		friend class buckets;
		friend class bucket_iterator;
		friend class const_bucket_iterator;

	public:

		typedef size2<float_type, S>                                    size_type;
		typedef vector2<float_type, S>                                  vector_type;
		typedef rectangle<float_type, S>                                rect_type;

		typedef T                                                       value_type;
		typedef typename boost::add_reference<value_type>::type         ref_type;
		typedef typename boost::add_const<value_type>::type             const_value_type;
		typedef typename boost::add_reference<const_value_type>::type   const_ref_type;

		#ifndef USE_STD_LIST
		typedef boostext::list<value_type>                              container;
		#else
		typedef std::list<value_type>                                   container;
		#endif

		typedef quadtree<T, float_type, S>                              _This;

		typedef boost::optional<_This>                                  opt;

	private:

		enum Type
		{
			UpperLeft = 0,
			UpperRight = 1,
			LowerLeft = 2,
			LowerRight = 3,

			Center = 4,
		};

		#ifdef STORE_INSTANCE
		/**
		 * This is the storage structure that exists once per "quadtree" instance,
		 * ie. for every instance of a whole tree.
		 */
		struct RootStorage
		{
			/// Pointer to the root node of the quadtree
			_This* const        root;

			/// The rectangle of the entire quadtree
			const rect_type     rect;

			/// The maximum depth this tree is allowed to have
			const std::size_t   maxDepth;
			/// The maximum number of values that are allowed per bucket
			const std::size_t   maxValues;

			RootStorage(_This* root, rect_type rect, std::size_t maxDepth, std::size_t maxValues)
				: root(root)
				, rect(rect)
				, maxDepth(maxDepth)
				, maxValues(maxValues)
			{}
		};
		#endif

		/**
		 * This structure models a sequence container that acts much like QList, ie.
		 * it stores an array of pointers to buckets, however the individual buckets
		 * are linked as well.
		 *
		 * Each bucket knows it's parent, its next sibling as well as its child-buckets.
		 * A bucket owns its children and deletes them when destroyed.
		 *
		 * Lookups using operator[] and first() are of complexity O(1).
		 * size() calculates the size in a loop and thus produces some overhead.
		 * Insertions and removals are of complexity O(1) in theory, however there is some more
		 * work involved, since sibling information must be updated as well.
		 */
		struct Buckets
		{
		private:

			/// Array of pointers to the child-buckets
			_This*   m_buckets[4];

		public:

			Buckets()
			{
				memset(m_buckets, NULL, sizeof(m_buckets));
			}

			~Buckets()
			{
				clear();
			}



			/**
			 * Removes all buckets from this array.
			 */
			void clear()
			{
				for(std::size_t i = 0; i < 4; ++i)
				{
					delete m_buckets[i];
					m_buckets[i] = NULL;
				}
			}

			/**
			 * @return the size of this array
			 */
			std::size_t size() const
			{
				std::size_t s = 0;
				for(std::size_t i = 0; i < 4; ++i)
					s += m_buckets[i] != NULL;

				return s;
			}

			/**
			 * @return the first valid (ie. existing) bucket.
			 */
			_This* first()
			{
				// Can be left uninitialized because the loop
				// will set it to something defined (either a valid
				// bucket or NULL
				_This* bucket;
				for(std::size_t i = 0; i < 4; ++i)
				{
					bucket = m_buckets[i];
					if(bucket != NULL)
						break;
				}
				return bucket;
			}

			/**
			 * @return the quadrant of the first exiting bucket
			 * @throws boostext::programming_error if there is no bucket
			 */
			Type firstType() const
			{
				for(std::size_t i = 0; i < 4; ++i)
					if(m_buckets[i] != NULL)
						return (Type)i;

				BOOSTEXT_THROW(boostext::programming_error("There is no bucket"));
			}

			/**
			 * @return the first existing bucket
			 */
			const _This* first() const
			{
				// Can be left uninitialized because the loop
				// will set it to something defined (either a valid
				// bucket or NULL
				_This* bucket;

				for(std::size_t i = 0; i < 4; ++i)
				{
					bucket = m_buckets[i];
					if(bucket != NULL)
						break;
				}

				return bucket;
			}

			/**
			 * @return the type of quadrant the given bucket lies in
			 */
			Type type(const _This* that) const
			{
				for(std::size_t i = 0; i < 4; ++i)
					if(m_buckets[i] == that)
						return (Type)i;

				BOOSTEXT_THROW(boostext::programming_error("There is no such bucket"));
			}



			/**
			 * @return the bucket at the given index
			 */
			_This* operator[](Type index)
			{
				#ifdef _DEBUG
				verify(index >= 0 && index <= 3)
				#endif

				return m_buckets[index];
			}

			/**
			 * @return the bucket at the given index
			 */
			const _This* operator[](Type index)const
			{
				#ifdef _DEBUG
				verify(index >= 0 && index <= 3)
				#endif

				return m_buckets[index];
			}



			/**
			 * Returns the next sibling of the given one.
			 */
			_This* next(Type current)
			{
				for(std::size_t i = current + 1; i < 4; ++i)
					if(m_buckets[i] != NULL)
						return m_buckets[i];

				return NULL;
			}

			/**
			 * Returns the next sibling of the given one.
			 */
			const _This* next(Type current) const
			{
				for(std::size_t i = current + 1; i < 4; ++i)
					if(m_buckets[i] != NULL)
						return m_buckets[i];

				return NULL;
			}



			/**
			 * Adds the bucket at the given index.
			 * @return the newly created bucket
			 */
			_This* add(_This* parent, Type index)
			{
				#ifdef _DEBUG
				verify(m_buckets[index] == NULL);
				#endif

				_This* bucket = new _This(*parent, index);
				m_buckets[index] = bucket;

				return bucket;
			}

			/**
			 * Removes and deletes the bucket at the given index.
			 */
			void remove(Type index)
			{
				_This* bucket = (*this)[index];
				if(!bucket)
					return;

				delete bucket;
				m_buckets[index] = NULL;
			}
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

	public:

		typedef typename container::iterator         flat_iterator;
		typedef typename container::const_iterator   const_flat_iterator;

		struct no_filter
			: public base_filter<no_filter, _This>
		{
			no_filter()
			{}

			/**
			 * Create a no_filter from any other filter.
			 */
			template <typename filter>
			no_filter(const filter&)
			{}

			template <typename Iter>
			bool operator()(const Iter& iter) const
			{ return true; }
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

		struct rect_filter
			: public base_filter<rect_filter, _This>
		{
			rect_type rect;

			rect_filter(rect_type rect)
				: rect(rect)
			{}

			/**
			 * Tests if any iterator intersects the stored rectangle.
			 * This function is meant for iterators only, because the value
			 * type usually doesn't need to implement a member function looseRect.
			 */
			template <typename T>
			bool operator()(const T& that) const
			{
				// The most notable difference to an ordinary quadtree is that every intersection
				// test must operate on the loose rectangle of a bucket
				return rect.intersects(that.looseRect());
			}

			/**
			 * Tests if a value_type intersects the stored rectangle.
			 * This test can be done against the values inside the tree.
			 */
			bool operator()(const_ref_type that) const
			{
				return rect.intersects(boundingRect(that));
			}
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

		/**
		 * This iterator models a forward, deep iterator. It prefers to move downwards the tree, and will only move
		 * side/up wards in case it has reached a leaf.
		 * Calling operator++ will perform the above, as does increment().
		 * However one might want to write custom code
		 * and doesn't want to put it in a filter, in order to skip a branch. In this case, calling increment_sidewards()
		 * has the same effect as returning false within the filter operation.
		 */
		template <typename T, typename bucket_filter = no_filter>
		class basic_bucket_iterator
			: public boost::iterator_facade<basic_bucket_iterator<T, bucket_filter>, T, boost::forward_traversal_tag>
		{
		private:

			T*              m_start;

			T*              m_node;

			#ifdef ITERATOR_RECT
			Type            m_type;
			std::size_t     m_depth;
			vector_type     m_center;
			#endif

			bucket_filter   m_filter;

		public:

			basic_bucket_iterator(T* start, T* node, const bucket_filter& filter = bucket_filter())
				: m_start(start)

				, m_node(node)

				#ifdef ITERATOR_RECT
				, m_type(m_node != NULL ? m_node->type() : Center)
				, m_center(m_node != NULL ? m_node->center() : vector_type())
				, m_depth(m_node != NULL ? m_node->bucketDepth() : 0)
				#endif

				, m_filter(filter)
			{
				if(m_node)
				{
					// We should skip those nodes that do not pass the test
					if(!pass())
						increment();
				}
			}

			/**
			 * This constructor is supplied to create a basic_bucket_iterator from another one
			 * that uses a different value_type. This constructor is created in order to create
			 * a const_iterator from a non-const iterator.
			 */
			template <typename O, typename F>
			basic_bucket_iterator(const basic_bucket_iterator<O, F>& that)
				: m_start(that.start())

				, m_node(that.node())

				#ifdef ITERATOR_RECT
				, m_type(m_node != NULL ? m_node->type() : Center)
				, m_center(m_node != NULL ? m_node->center() : vector_type())
				, m_depth(m_node != NULL ? m_node->bucketDepth() : 0)
				#endif

				, m_filter(that.filter())
			{
				if(m_node)
				{
					// We should skip those nodes that do not pass the test
					if(!pass())
						increment();
				}
			}



			/**
			 * @return the rectangle of the current bucket
			 * @throw  boostext::programming_error in case the iterator points to the end of the tree
			 */
			rect_type rect() const
			{
				verify(m_node != NULL);

				#ifdef ITERATOR_RECT
				size_type childSize = size(m_node->rootRect(), m_depth);
				// Construct the rectangle around the center
				return rect_type::center(m_center, childSize);
				#else
				// Let the node construct it's bounding rectangle
				return m_node->rect();
				#endif
			}

			/**
			 * @return the loose rectangle of the current bucket (twice the bounding rectangle's width
			 */
			rect_type looseRect() const
			{
				verify(m_node != NULL);

				#ifdef ITERATOR_RECT
				size_type childSize = size(m_node->rootRect(), m_depth);
				// Construct the rectangle around the center
				return rect_type::center(m_center, 2.0 * childSize);
				#else
				// Let the node construct it's bounding rectangle
				return m_node->looseRect();
				#endif
			};

			/**
			 * @return the depth of the current bucket
			 * @throw  boostext::programming_error in case the iterator points to the end of the tree
			 */
			std::size_t depth() const
			{
				verify(m_node != NULL);

				#ifdef ITERATOR_RECT
				return m_depth;
				#else
				return m_node->depth();
				#endif
			}

			/**
			 * @return the quadrant of the parent, this bucket lies inside
			 * @throw  boostext::programming_error in case the iterator points to the end of the tree
			 */
			Type type() const
			{
				verify(m_node != NULL);

				#ifdef ITERATOR_RECT
				return m_type;
				#else
				return m_node->type();
				#endif
			}



			/**
			 * @return a reference to the current bucket
			 * @throw  boostext::programming_error in case the iterator points to the end of the tree
			 */
			reference dereference() const
			{
				verify(m_node != NULL);

				return *m_node;
			}

			/**
			 * Tests if this bucket is equal to the other one.
			 */
			bool equal(const basic_bucket_iterator<T, bucket_filter>& that) const
			{
				return m_start == that.m_start && m_node == that.m_node;
			}

			/**
			 * Advances the iterator to the next bucket in the tree.
			 * The iterator will move to the next child, to a sibling, or a sibling,
			 * of any parent, depending on those buckets being present or not (in the given order).
			 *
			 * @throw  boostext::programming_error in case the iterator points to the end of the tree
			 */
			void increment()
			{
				verify(m_node != NULL);

				// We travel the tree downwards and test if there are more buckets there
				T* down = m_node->m_buckets.first();
				if(down)
				{
					m_node   = down;
					#ifdef ITERATOR_RECT
					++m_depth;
					m_type   = m_node->type();
					m_center = childCenter(m_node->rootRect(), m_center, m_type, m_depth);
					#endif

					if(pass())
						return;
				}

				// There is nothing beneath this bucket: Advance to the next sibling or
				// (if there is no sibling) to the next sibling of a parent.
				increment_sidewards();
			}

			/**
			 * Advances the iterator to the next sibling bucket.
			 * If there is no sibling, the iterator is moved upwards and to a sibling of any of the bucket's
			 * parents.
			 */
			void increment_sidewards()
			{
				do
				{
					// It is forbidden to travel past the starting node (that means up- or sidewards the starting node)
					// Reaching the start node again counts as having reached the end
					if(m_node == m_start)
					{
						m_node = NULL;
						return;
					}

					// Try to find the next sibling of the current bucket
					// (which is defined as the next one)
					T* sibling = m_node->sibling();

					if(sibling)
					{
						#ifdef ITERATOR_RECT
						// First, we calculate the parent rectangle for the OLD bucket
						m_center = parentCenter(m_node->rootRect(), m_center, m_type, m_depth);
						m_type   = sibling->type();
						// And then we calculate the child rectangle for the new bucket (because we've changed m_type...)
						m_center = childCenter(m_node->rootRect(), m_center, m_type, m_depth);
						#endif

						m_node = sibling;

						// Apply the filter to the sibling to test
						// if that one is wanted or not. If it's not
						// wanted, we simply treat it as not available and go to the next sibling
						if(pass())
							return;

						// The sibling didn't pass the test, thus we skip this bucket and let the node advance
						// to the next one...
					}
					else
					{
						// There is no sibling bucket, we must go upwards
						m_node = m_node->m_parent;

						#ifdef ITERATOR_RECT
						m_center = parentCenter(m_node->rootRect(), m_center, m_type, m_depth);
						m_type   = m_node->type();
						--m_depth;
						#endif
					}
				} while(true);
			}



			/**
			 * Test if this iterator is valid or not.
			 */
			operator bool() const
			{
				return m_node != NULL;
			}

			/**
			 * Returns a pointer to the starting bucket of this iterator.
			 */
			T* start() const
			{
				return m_start;
			}

			/**
			 * @return the node this iterator points to.
			 */
			T* node() const
			{
				return m_node;
			}

			/**
			 * @return the bucket-filter of this iterator
			 */
			const bucket_filter& filter() const
			{
				return m_filter;
			}

		private:

			/**
			 * Test if the current node passes the test, performed by the filter
			 * or not.
			 *
			 * @warning   This function assumes that m_node is set to an existing (!) bucket
			 */
			bool pass() const
			{
				verify(m_node != NULL);

				return m_filter(*this) == true;
			}
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

		typedef basic_bucket_iterator<_This>         bucket_iterator;
		typedef basic_bucket_iterator<_This const>   const_bucket_iterator;

		/**
		 * This iterator models a forward, deep iterator that iterates over all values of the tree.
		 * It uses a bucket_iterator to perform the actual deep iteration, and a flat_iterator to
		 * iterate over all values of the current bucket.
		 * The iterator is designed to always point to an existing element (and thus can be dereferenced),
		 * or toward the end. Empty buckets are skipped entirely. Due to this fact, some iterating must be done
		 * during construction in most cases, since the first buckets of a tree are usually empty (values are inserted as deep as possible),
		 * and the iterator must find the first bucket with values in it.
		 */
		template <typename bucket_iterator, typename flat_iterator, typename T>
		class basic_value_iterator
			: public boost::iterator_facade<basic_value_iterator<bucket_iterator, flat_iterator, T>, T, boost::forward_traversal_tag>
		{
		public:

			typedef bucket_iterator   bucket_iterator_t;
			typedef flat_iterator     flat_iterator_t;

		private:

			bucket_iterator   m_bucket;
			bucket_iterator   m_end;
			flat_iterator     m_element;

		public:

			basic_value_iterator(bucket_iterator bucket, bucket_iterator end, flat_iterator element)
				: m_bucket(bucket)
				, m_end(end)
				, m_element(element)
			{
				// It is possible that we're pointing to a bucket that has no elements on it's own.
				// If this is the case, we iterate over all buckets until we find a non-empty bucket
				// or reach the end. This way, the constructed iterator points to a bucket that has an
				// element and thus can be dereferenced, unless it points to the end.
				if(m_bucket != m_end)
				{
					// There are buckets to iterate: Let's see if this bucket has no children OR if the current
					// element doesn't pass the filter test
					if(m_element == m_bucket->flatEnd() || m_bucket.filter()(*m_element) == false)
						advance_to_next_element();
				}
			}

			/**
			 * Create a basic_deep_iterator from another one that uses a different value_type
			 * (and possibly different iterators). This constructor is required to convert
			 * a non-const iterator to a const_iterator.
			 */
			template <typename T1, typename T2, typename T3>
			basic_value_iterator(const basic_value_iterator<T1, T2, T3>& that)
				: m_bucket(that.bucket())
				, m_end(that.end())
				, m_element(that.element())
			{
				// It is possible that we're pointing to a bucket that has no elements on it's own.
				// If this is the case, we iterate over all buckets until we find a non-empty bucket
				// or reach the end. This way, the constructed iterator points to a bucket that has an
				// element and thus can be dereferenced, unless it points to the end.
				if(m_bucket != m_end)
				{
					// There are buckets to iterate: Let's see if this bucket has no children OR if the current
					// element doesn't pass the filter test
					if(m_element == m_bucket->flatEnd() || m_bucket.filter()(*m_element) == false)
						advance_to_next_element();
				}
			}



			/**
			 * Dereferences this iterator.
			 */
			reference dereference() const
			{
				verify(m_bucket != m_end);
				verify(m_element != m_bucket->flatEnd());

				return *m_element;
			}

			/**
			 * Tests if this iterator is equal to the other one.
			 */
			bool equal(const basic_value_iterator<bucket_iterator, flat_iterator, T>& that) const
			{
				// There is some more logic required:
				// It's undefined where the element iterator should point to, when
				// this iterator does not point to a valid element and thus we only
				// compare the buckets in that case
				if(m_bucket == m_end)
					return m_bucket == that.m_bucket && m_end == that.m_end;
				else
					return m_bucket == that.m_bucket && m_end == that.m_end && m_element == that.m_element;
			}

			/**
			 * Advances this iterator to the next value inside the tree.
			 */
			void increment()
			{
				++m_element;

				if(m_element == m_bucket->flatEnd())
					advance_to_next_element();
			}

			/**
			 * @return iterator to the current bucket.
			 */
			bucket_iterator bucket() const
			{
				return m_bucket;
			}

			/**
			 * @return the iterator past the end of all buckets.
			 */
			bucket_iterator end() const
			{
				return m_end;
			}

			/**
			 * @return the element of this iterator.
			 */
			flat_iterator element() const
			{
				return m_element;
			}

		private:

			/**
			 * Advances this iterator so that it points to the next bucket containing elements.
			 * (It's not enough to simply advance the iterator to the next bucket, since it
			 * might not contain any elements).
			 */
			void advance_to_next_element()
			{
				// Find the next non-empty bucket
				while(true)
				{
					++m_bucket;

					// If there are no more buckets, then we can stop here
					if(m_bucket == m_end)
						return;

					if(m_bucket->bucketHasValues())
						break;
				}

				// And save the iterator to the first real element of that bucket
				m_element = m_bucket->flatBegin();
			}
		};
		/////////////////////////////////////////////////////////////////////////////////////////////

		typedef basic_value_iterator<bucket_iterator, flat_iterator, value_type>                     iterator;
		typedef basic_value_iterator<const_bucket_iterator, const_flat_iterator, const_value_type>   const_iterator;

	public:

		static const uint8   defaultMaxValues = 20;
		static const uint8   defaultMaxDepth  = 8;

	private:

		#ifdef STORE_INSTANCE
		RootStorage*          m_storage;
		#else
		const uint8       m_depth;
		const uint8       m_maxDepth;
		const uint8       m_maxValues;
		const uint8       m_type;

		const rect_type   m_rect;
		#endif

		/// Pointer to the parent
		_This*            m_parent;

		/// Pointers to the children
		Buckets           m_buckets;

		/// Actual sequence of values
		container         m_values;

	private:

		quadtree(_This& parent, Type type)
			#ifdef STORE_INSTANCE
			: m_storage(parent.m_storage)
			#else
			: m_depth(parent.m_depth + 1)
			, m_maxDepth(parent.m_maxDepth)
			, m_maxValues(parent.m_maxValues)
			, m_type(type)
			, m_rect(createChildRect(parent.rect(), type))
			#endif

			, m_parent(&parent)
		{
			#ifndef STORE_INSTANCE
			// We should never create nodes past the maximum depth
			verify(m_depth <= m_maxDepth);
			#endif
		}

	public:

		/**
		 * Creates an empty quadtree.
		 */
		quadtree(rect_type rect, uint8 maxDepth = defaultMaxDepth, uint8 maxValues = defaultMaxValues)
			#ifdef STORE_INSTANCE
			: m_storage(0)
			#else
			: m_depth(0)
			, m_maxDepth(maxDepth)
			, m_maxValues(maxValues)
			, m_type(Center)
			, m_rect(rect)
			#endif

			, m_parent(NULL)
		{
			// It's unreasonable to allow less than 1 value per bucket
			verify(maxValues >= 1);

			#ifdef STORE_INSTANCE
			m_storage = new RootStorage(this, rect, maxDepth, maxValues);
			#endif
		}

		/**
		 * Creates a quadtree with one element.
		 */
		quadtree(rect_type rect, uint8 maxDepth, uint8 maxValues, const_ref_type value)
			#ifdef STORE_INSTANCE
			: m_storage(0)
			#else
			: m_depth(0)
			, m_maxDepth(maxDepth)
			, m_maxValues(maxValues)
			, m_type(Center)
			, m_rect(rect)
			#endif

			, m_parent(NULL)

			, m_values(value, 1)
		{
			// It's unreasonable to allow less than 1 value per bucket
			verify(maxValues >= 1);

			#ifdef STORE_INSTANCE
			m_storage = new RootStorage(this, rect, maxDepth, maxValues);
			#endif
		}

		/**
		 * Creates a quadtree from a list of elements.
		 * The elements are automatically added to the quadtree.
		 */
		quadtree(rect_type rect, uint8 maxDepth, uint8 maxValues, const container& values)
			#ifdef STORE_INSTANCE
			: m_storage(0)
			#else
			: m_depth(0)
			, m_maxDepth(maxDepth)
			, m_maxValues(maxValues)
			, m_type(Center)
			, m_rect(rect)
			#endif

			, m_parent(NULL)
		{
			// It's unreasonable to allow less than 1 value per bucket
			verify(maxValues >= 1);

			#ifdef STORE_INSTANCE
			m_storage = new RootStorage(this, rect, maxDepth, maxValues);
			#endif

			insert(values);
		}

		template <typename Iter>
		quadtree(rect_type rect, uint8 maxDepth, uint8 maxValues, const Iter& begin, const Iter& end)
			#ifdef STORE_INSTANCE
			: m_storage(0)
			#else
			: m_depth(0)
			, m_maxDepth(maxDepth)
			, m_maxValues(maxValues)
			, m_type(Center)
			, m_rect(rect)
			#endif

			, m_parent(NULL)
		{
			// It's unreasonable to allow less than 1 value per bucket
			verify(maxValues >= 1);

			#ifdef STORE_INSTANCE
			m_storage = new RootStorage(this, rect, maxDepth, maxValues);
			#endif

			insert(begin, end);
		}

		/**
		 * Destroys this quadtree.
		 */
		~quadtree()
		{
			clear();

			#ifdef STORE_INSTANCE
			if(!m_parent)
				delete m_storage;
			#endif
		}



		/**
		 * @return the rectangle of the entire quadtree
		 */
		rect_type rootRect() const
		{
			return m_storage->rect;
		}

		/**
		 * @return the type of node
		 */
		Type type() const
		{
			#ifdef STORE_INSTANCE
			if(!m_parent)
				return Center;

			return m_parent->m_buckets.type(this);
			#else
			return static_cast<Type>(m_type);
			#endif
		}

		/**
		 * Returns the bounding rectangle of this node.
		 */
		rect_type rect() const
		{
			#ifdef STORE_INSTANCE
			if(!m_parent)
				return m_storage->rect;

			rect_type rect = m_parent->rect();
			return createChildRect(rect, type());
			#else
			return m_rect;
			#endif
		}

		/**
		 * @return the center of this node
		 */
		vector_type center() const
		{
			return rect().center();
		}

		/**
		 * @return the number of elements in this tree.
		 */
		std::size_t size() const
		{
			return numValues();
		}

		/**
		 * Returns the depth of the entire tree.
		 */
		uint8 depth() const
		{
			std::size_t depth = bucketDepth();

			// Thanks to the bucket iterator, we are able to iterate over all
			// buckets without using recursion (and thus are able to avoid a stack
			// overflow)
			const_bucket_iterator i   = bucketBegin();
			const_bucket_iterator end = bucketEnd();
			while(i != end)
			{
				// We only take the bucket's depth if it has no children
				// (only in this case there is a chance that this will be the final
				// tree's depth).
				if(i->bucketNumBuckets() == 0)
					depth = std::max(depth, i->bucketDepth());

				++i;
			}

			return depth;
		}

		/**
		 * Returns the maximum depth of this tree.
		 * There won't be any buckets/nodes past this depth.
		 */
		std::size_t maxDepth() const
		{
			#ifdef STORE_INSTANCE
			return m_storage->maxDepth;
			#else
			return m_maxDepth;
			#endif
		}

		/**
		 * @return the depth of this bucket.
		 */
		std::size_t bucketDepth() const
		{
			#ifdef STORE_INSTANCE
			if(!m_parent)
				return 0;

			const _This* node = this;
			std::size_t depth = 0;
			while(node->m_parent)
			{
				node = node->m_parent;
				++depth;
			}

			return depth;
			#else
			return m_depth;
			#endif
		}

		/**
		 * Returns the number of buckets in this tree (including this one).
		 */
		std::size_t numBuckets() const
		{
			std::size_t buckets = 0;

			const_bucket_iterator i   = bucketBegin();
			const_bucket_iterator end = bucketEnd();
			while(i != end)
			{
				++i;
				++buckets;
			}

			return buckets;
		}

		/**
		 * Returns the number of buckets of this bucket.
		 * This function has a complexity of O(n) (n <= 4).
		 */
		std::size_t bucketNumBuckets() const
		{
			return m_buckets.size();
		}

		/**
		 * Returns the number of elements in this tree.
		 */
		std::size_t numValues() const
		{
			std::size_t elements = 0;

			const_bucket_iterator i   = bucketBegin();
			const_bucket_iterator end = bucketEnd();
			while(i != end)
			{
				elements += i->bucketNumValues();
				++i;
			}

			return elements;
		}

		/**
		 * Returns the number of values of this bucket.
		 */
		std::size_t bucketNumValues() const
		{
			return m_values.size();
		}

		/**
		 * Tests if the bucket is empty or not.
		 */
		bool bucketHasValues() const
		{
			return m_values.isEmpty() == false;
		}

		/**
		 * Returns the maximum number of elements per node.
		 * A node is allowed to exceed this limit if it's at the maximum depth
		 * (to avoid infinite recursion in case the maximum number of elements are
		 * all inserted at the same position).
		 */
		std::size_t maxValues() const
		{
			#ifdef STORE_INSTANCE
			return m_storage->maxValues;
			#else
			return m_maxValues;
			#endif
		}



		/**
		 * Returns the first value in this bucket or branch.
		 */
		ref_type first()
		{
			if(bucketHasValues())
			{
				return m_values.first();
			}
			else
			{
				iterator i = begin();
				iterator e = end();
				if(i == e)
					BOOSTEXT_THROW(boostext::programming_error("Bucket is empty"));

				// The iterator is advanced to the first bucket with a value during construction
				// So we can simply dereference it, in case it isn't pointing towards the end
				return *i;
			}
		}

		/**
		 * Returns the first value in this bucket or branch.
		 */
		const_ref_type first() const
		{
			if(bucketHasValues())
			{
				return m_values.first();
			}
			else
			{
				const_iterator i = begin();
				const_iterator e = end();
				if(i == e)
					BOOSTEXT_THROW(boostext::programming_error("Bucket is empty"));

				// The iterator is advanced to the first bucket with a value during construction
				// So we can simply dereference it, in case it isn't pointing towards the end
				return *i;
			}
		}



		/**
		 * Insert the given value into the quadtree.
		 */
		void insert(const_ref_type value)
		{
			verify(!m_parent);

			rect_type rect = this->rect();

			// The user has access to all buckets and thus could try to insert an item
			// in the wrong place.
			if(!rect.intersects(boundingRect(value)))
				BOOSTEXT_THROW(boostext::programming_error("Value is outside bounding rectangle and cannot be added to this bucket"));

			insert(this, rect, Center, 0, value);
		}


		/**
		 * Inserts all values from the given container into this quadtree.
		 */
		void insert(const container& that)
		{
			insert(that.begin(), that.end());
		}

		/**
		 * Inserts all values from the given range into this quadtree.
		 */
		template <typename Iter>
		void insert(Iter begin, Iter end)
		{
			while(begin != end)
			{
				insert(*begin);
				++begin;
			}
		}

		/**
		 * Searches the first element at the given position and returns an iterator to it.
		 * Otherwise returns an iterator to the end of the tree.
		 */
		typename rect_filter::iterator find(vector_type pos)
		{
			return find(rect_type::corners(pos, pos));
		}

		/**
		 * Searches the first element at the given position and returns an iterator to it.
		 * Otherwise returns an iterator to the end of the tree.
		 */
		typename rect_filter::const_iterator find(vector_type pos) const
		{
			return find(rect_type::corners(pos, pos));
		}

		/**
		 * Searches the first values that intersects the given rectangle.
		 * The returned iterator can be used to iterate over all values that do so.
		 */
		typename rect_filter::iterator find(rect_type rect)
		{
			#ifdef STORE_INSTANCE
			// find may only be called on the root node
			verify(this == m_storage->root);
			#endif

			// The basic_iterator does all the work for us
			// The only thing left to do is finding the first item
			// in a bucket that matches the filter as well...
			rect_filter filter(rect);
			rect_filter::iterator it  = begin(filter);
			rect_filter::iterator end = this->end(filter);
			while(it != end)
			{
				if(rect.intersects(boundingRect(*it)))
					break;

				++it;
			}

			return it;
		}

		/**
		 * Searches the first values that intersects the given rectangle.
		 * The returned iterator can be used to iterate over all values that do so.
		 */
		typename rect_filter::const_iterator find(rect_type pos) const
		{
			#ifdef STORE_INSTANCE
			// find may only be called on the root node
			verify(this == m_storage->root);
			#endif

			// The basic_iterator does all the work for us
			// The only thing left to do is finding the first item
			// in a bucket that matches the filter as well...
			rect_filter filter(rect);
			rect_filter::const_iterator it  = begin(filter);
			rect_filter::const_iterator end = this->end(filter);
			while(it != end)
			{
				if(rect.intersects(boundingRect(*it)))
					break;

				++it;
			}

			return it;
		}

		/**
		 * Finds the item with exactly the given rectangle.
		 */
		typename rect_filter::iterator findExact(rect_type rect)
		{
			#ifdef STORE_INSTANCE
			// find may only be called on the root node
			verify(this == m_storage->root);
			#endif

			// The basic_iterator does all the work for us
			// The only thing left to do is finding the first item
			// in a bucket that matches the filter as well...
			rect_filter filter(rect);
			rect_filter::iterator it  = begin(filter);
			rect_filter::iterator end = this->end(filter);
			while(it != end)
			{
				if(rect == boundingRect(*it))
					break;

				++it;
			}

			return it;
		}

		/**
		 * Finds the item with exactly the given rectangle.
		 */
		typename rect_filter::const_iterator findExact(rect_type rect) const
		{
			#ifdef STORE_INSTANCE
			// find may only be called on the root node
			verify(this == m_storage->root);
			#endif

			// The basic_iterator does nearly all the work for us
			// There are 2 things left to do:
			// - Compare all values against the required rectangle
			// - Stop when the bucket is too small (not implemented yet)
			rect_filter filter(rect);
			rect_filter::const_iterator it  = begin(filter);
			rect_filter::const_iterator end = this->end(filter);
			while(it != end)
			{
				if(rect == boundingRect(*it))
					break;

				++it;
			}

			return it;
		}

		/**
		 * Erases the given element.
		 * Returns an iterator to the next element in place.
		 */
		template <typename T, typename flat_iter, typename bucket_iter>
		basic_value_iterator<T, flat_iter, bucket_iter> erase(const basic_value_iterator<T, flat_iter, bucket_iter>& that)
		{
			basic_value_iterator<T, flat_iter, bucket_iter> tmp = that;
			++tmp;

			// Access the actual bucket the iterator is referring to
			// and tell that bucket to remove the given value from it's list
			// of values
			that.bucket()->erase(that.element());

			return tmp;
		}

		/**
		 * Erases the given value.
		 * Returns a flat iterator to the next value.
		 */
		flat_iterator erase(const flat_iterator& that)
		{
			return m_values.erase(that);
		}

		/**
		 * Erases the given bucket.
		 * Returns an iterator to the next bucket in place
		 * (either a sibling or a sibling of any of the parents).
		 */
		template <typename T, typename filter>
		basic_bucket_iterator<T, filter> erase(const basic_bucket_iterator<T, filter>& that)
		{
			// We want to find the next iterator in place, however
			// the bucket we want to erase might contain child nodes
			// (which causes the iterator to travel downwards).
			// Since the bucket is destroyed after this operation, we simply
			// remove all child buckets before incrementing the iterator
			that->clear();

			basic_bucket_iterator<T, filter> tmp = that;
			++tmp;

			that->m_parent->erase(that->type());

			return tmp;
		}



		/**
		 * Returns a deep iterator to the first element of this tree.
		 */
		iterator begin()
		{
			return iterator(bucketBegin(), bucketEnd(), flatBegin());
		}

		/**
		 * Returns a deep iterator past the last element of this tree.
		 */
		iterator end()
		{
			return iterator(bucketEnd(), bucketEnd(), flatEnd());
		}

		/**
		 * Returns a deep iterator to the first element of this tree.
		 */
		const_iterator begin() const
		{
			return const_iterator(bucketBegin(), bucketEnd(), flatBegin());
		}

		/**
		 * Returns a deep iterator past the last element of this tree.
		 */
		const_iterator end() const
		{
			return const_iterator(bucketEnd(), bucketEnd(), flatEnd());
		}



		/**
		 * Returns a deep iterator to the first element of this tree.
		 */
		template <typename bucket_filter>
		basic_value_iterator<basic_bucket_iterator<_This, bucket_filter>, flat_iterator, _This> begin(const bucket_filter& filter)
		{
			return basic_value_iterator<basic_bucket_iterator<_This, bucket_filter>, flat_iterator, _This>(bucketBegin(filter), bucketEnd(filter), flatBegin());
		}

		/**
		 * Returns a deep iterator past the last element of this tree.
		 */
		template <typename bucket_filter>
		basic_value_iterator<basic_bucket_iterator<_This, bucket_filter>, flat_iterator, _This> end(const bucket_filter& filter)
		{
			return basic_value_iterator<basic_bucket_iterator<_This, bucket_filter>, flat_iterator, _This>(bucketEnd(filter), bucketEnd(filter), flatEnd());
		}

		/**
		 * Returns a deep iterator to the first element of this tree.
		 */
		template <typename bucket_filter>
		basic_value_iterator<basic_bucket_iterator<_This const, bucket_filter>, const_flat_iterator, _This const> begin(const bucket_filter& filter) const
		{
			return basic_value_iterator<basic_bucket_iterator<_This const, bucket_filter>, const_flat_iterator, _This const>(bucketBegin(filter), bucketEnd(filter), flatBegin());
		}

		/**
		 * Returns a deep iterator past the last element of this tree.
		 */
		template <typename bucket_filter>
		basic_value_iterator<basic_bucket_iterator<const _This, bucket_filter>, const_flat_iterator, _This const> end(const bucket_filter& filter) const
		{
			return basic_value_iterator<basic_bucket_iterator<_This const, bucket_filter>, const_flat_iterator, _This const>(bucketEnd(filter), bucketEnd(filter), flatEnd());
		}



		/**
		 * Returns an iterator to the first bucket of this tree.
		 */
		bucket_iterator bucketBegin()
		{
			return bucket_iterator(this, this);
		}

		/**
		 * Returns an iterator past the last bucket of this tree.
		 */
		bucket_iterator bucketEnd()
		{
			return bucket_iterator(this, NULL);
		}

		/**
		 * @return an iterator to the first bucket of this tree.
		 */
		const_bucket_iterator bucketBegin() const
		{
			return const_bucket_iterator(this, this);
		}

		/**
		 * Returns an iterator past the last bucket of this tree.
		 */
		const_bucket_iterator bucketEnd() const
		{
			return const_bucket_iterator(this, NULL);
		}



		/**
		 * Returns an iterator to the first bucket of this tree.
		 */
		template <typename bucket_filter>
		basic_bucket_iterator<_This, bucket_filter> bucketBegin(const bucket_filter& filter)
		{
			return basic_bucket_iterator<_This, bucket_filter>(this, this, filter);
		}

		/**
		 * Returns an iterator past the last bucket of this tree.
		 */
		template <typename bucket_filter>
		basic_bucket_iterator<_This, bucket_filter> bucketEnd(const bucket_filter& filter)
		{
			return basic_bucket_iterator<_This, bucket_filter>(this, NULL, filter);
		}

		/**
		 * @return an iterator to the first bucket of this tree.
		 */
		template <typename bucket_filter>
		basic_bucket_iterator<_This const, bucket_filter> bucketBegin(const bucket_filter& filter) const
		{
			return basic_bucket_iterator<_This const, bucket_filter>(this, this, filter);
		}

		/**
		 * Returns an iterator past the last bucket of this tree.
		 */
		template <typename bucket_filter>
		basic_bucket_iterator<_This const, bucket_filter> bucketEnd(const bucket_filter& filter) const
		{
			return basic_bucket_iterator<_This const, bucket_filter>(this, NULL, filter);
		}



		/**
		 * Returns an iterator to the first element of this bucket.
		 */
		flat_iterator flatBegin()
		{
			return m_values.begin();
		}

		/**
		 * Returns an iterator past the last element of this bucket.
		 */
		flat_iterator flatEnd()
		{
			return m_values.end();
		}

		/**
		 * Returns an iterator to the first element of this bucket.
		 */
		const_flat_iterator flatBegin() const
		{
			return m_values.begin();
		}

		/**
		 * Returns an iterator past the last element of this bucket.
		 */
		const_flat_iterator flatEnd() const
		{
			return m_values.end();
		}



		/**
		 * Removes all elements and buckets from this tree.
		 */
		void clear()
		{
			m_values.clear();
			m_buckets.clear();
		}

	private:

		/**
		 * Returns the type of bucket the given position lies inside.
		 *
		 * @param pos   the position to test
		 */
		Type type(const vector_type pos) const
		{
			return type(rect(), pos);
		}

		/**
		 * Returns the type of bucket the given position lies inside.
		 *
		 * @param rect   the rectangle to test against
		 * @param pos    the position to test
		 */
		Type type(rect_type rect, const vector_type pos) const
		{
			vector_type center = rect.center();

			// We can use some simple logic to determine the type of bucket the given position lies inside
			// We don't need to calculate all four rectangles and to a full intersection test: we simply test
			// each axis against the center of this bucket's rectangle and then deduce the type from the result
			if(pos.y <= center.y)
				if(pos.x <= center.x)
					return UpperLeft;
				else
					return UpperRight;
			else
				if(pos.x <= center.x)
					return LowerLeft;
				else
					return LowerRight;
		}

		/**
		 * Tries to find the bucket of the given type and returns it.
		 * Otherwise creates a new bucket of that type first.
		 */
		_This* bucket(Type type)
		{
			_This* b = m_buckets[type];
			if(!b)
				b = m_buckets.add(this, type);

			return b;
		}

		/**
		 * Returns a pointer to the bucket of the given type or NULL if
		 * that bucket doesn't exist (yet).
		 */
		_This* find(Type type)
		{
			return m_buckets[type];
		}

		/**
		 * Returns a pointer to the bucket of the given type or NULL if
		 * that bucket doesn't exist (yet).
		 */
		const _This* find(Type type) const
		{
			return m_buckets[type];
		}

		/**
		 * @return the next sibling bucket or NULL if there isn't any
		 */
		_This* sibling()
		{
			if(!m_parent)
				return NULL;

			return m_parent->m_buckets.next(type());
		}

		/**
		 * @return the next sibling bucket or NULL if there isn't any
		 */
		const _This* sibling() const
		{
			if(!m_parent)
				return NULL;

			return m_parent->m_buckets.next(type());
		}

		/**
		 * Inserts the given value in the tree.
		 *
		 * @param node    the node to insert the value
		 * @param rect    the rectangle of this node
		 * @param type    the type of this node, compared to the parent
		 * @param depth   the depth of this node
		 * @param value   the value to insert
		 */
		static void insert(_This* node, rect_type rect, Type type, std::size_t depth, const_ref_type value)
		{
			vector_type pos            = position(value);
			size_type   itemSize       = boundingRect(value).size();
			size_type   bucketSize     = rect.size();
			size_type   nextBucketSize = bucketSize / 2.0;

			while(true)
			{
				// We will travel downwards as long as it is possible (ie. there are buckets)
				// AND as long as the item's size is smaller or equal to the bucket's size
				if(node->bucketNumBuckets() > 0 &&
					itemSize.width <= nextBucketSize.width && itemSize.height <= nextBucketSize.height)

				// We will travel downwards to find the deepest node possible, in order to insert this item
				// Note: Inserting stuff in the deepest bucket increases memory usage, but decreases iteration time
				//       for evenly distributed stuff.
				//if(depth < node->maxDepth() && itemSize.width <= nextBucketSize.width && itemSize.height <= nextBucketSize.height)
				{
					// Delegate to the corresponding child

					// Find out in which quadrant that child lies inside
					type = node->type(rect, pos);
					// Calculate the rectangle of the next child
					// As well as the size for the next bucket
					rect = createChildRect(rect, type);
					bucketSize = nextBucketSize;
					nextBucketSize = bucketSize / 2.0;
					// Advance to the next child
					node = node->bucket(type);
					// Update the depth of the child
					++depth;
				}
				else
				{
					// Insert here
					node->m_values.push_front(value);

					// Split the tree in case there are too many children
					if(node->m_values.size() > node->maxValues() && depth < node->maxDepth())
						node->split(rect, type, depth);

					break;
				}
			}
		}

		/**
		 * Creates child-nodes and inserts ALL values into those childs.
		 *
		 * @param rect    the rectangle of this node
		 * @param type    the type of this node, compared to the parent
		 * @param depth   the depth of this node
		 */
		void split(rect_type rect, Type type, std::size_t depth)
		{
			#ifdef _DEBUG
			// This function shall only be called in case we should hold more values
			// than we're supposed to hold
			verify(m_values.size() >= maxValues());
			#endif

			size_type bucketSize = rect.size();
			size_type nextBucketSize = bucketSize / 2.0;

			// Insert those values that intersect our rectangle, the others will
			// be ignored and should be inserted in another one
			for(flat_iterator i = m_values.begin(); i != m_values.end();)
			{
				ref_type value = *i;
				size_type itemSize = boundingRect(*i).size();

				if(itemSize.width <= nextBucketSize.width && itemSize.height <= nextBucketSize.height)
				{
					// In order to actually call insert on the child, we must supply it with
					// its rectangle, depth and relation to the parent, but all of it is calculated
					// in no time
					vector_type pos     = position(*i);

					Type childType      = this->type(rect, pos);
					rect_type childRect = createChildRect(rect, childType);
					_This* b = bucket(childType);

					insert(b, childRect, childType, depth + 1, *i);

					i = m_values.erase(i);
				}
				else
				{
					++i;
				}
			}
		}

		/**
		 * Erases the bucket at the given position.
		 */
		void erase(Type type)
		{
			m_buckets.remove(type);
		}

		/**
		 * Creates the bounding rectangle that covers a fourth of the
		 * given parent rectangle's area.
		 */
		static rect_type createChildRect(const _This* parent, Type type)
		{
			return createChildRect(parent->rect(), type);
		}

		/**
		 * Creates the bounding rectangle that covers a fourth of the
		 * given parent rectangle's area.
		 */
		static rect_type createChildRect(rect_type rect, Type type)
		{
			switch(type)
			{
			case UpperLeft:
				return rect_type::pointSize(rect.left(),
					rect.top(),
					rect.width() / 2,
					rect.height() / 2);
			case UpperRight:
				return rect_type::pointSize(rect.left() + rect.width() / 2,
					rect.top(),
					rect.width() / 2,
					rect.height() / 2);
			case LowerLeft:
				return rect_type::pointSize(rect.left(),
					rect.top() + rect.height() / 2,
					rect.width() / 2,
					rect.height() / 2);
			case LowerRight:
				return rect_type::pointSize(rect.left() + rect.width() / 2,
					rect.top() + rect.height() / 2,
					rect.width() / 2,
					rect.height() / 2);
			default:
				BOOSTEXT_THROW(boostext::invalid_value_exception(type));
			}
		}

		/**
		 * @param rect     the rectangle of the entire quadtree
		 * @param center   the center of the parent node
		 * @param type     the quadrant of the child
		 * @param depth    the depth of the child
		 *
		 * @return the center of the child quadrant
		 */
		static vector_type childCenter(rect_type rect, vector_type center, Type type, std::size_t depth)
		{
			size_type childSize = size(rect, depth);

			switch(type)
			{
			case UpperLeft:  return center + vector_type(-1 * childSize.width / 2, -1 * childSize.height / 2);
			case UpperRight: return center + vector_type( 1 * childSize.width / 2, -1 * childSize.height / 2);
			case LowerLeft:  return center + vector_type(-1 * childSize.width / 2,  1 * childSize.height / 2);
			case LowerRight: return center + vector_type( 1 * childSize.width / 2,  1 * childSize.height / 2);
			default: BOOSTEXT_THROW(boostext::invalid_value_exception(type));
			}
		}

		/**
		 * @param rect     the rectangle of the entire quadtree
		 * @param center   the center of the child node
		 * @param type     the quadrant of the child
		 * @param depth    the depth of the child
		 */
		static vector_type parentCenter(rect_type rect, vector_type center, Type type, std::size_t depth)
		{
			size_type childSize = size(rect, depth);

			switch(type)
			{
			case UpperLeft:  return center + vector_type( 1 * childSize.width / 2,  1 * childSize.height / 2);
			case UpperRight: return center + vector_type(-1 * childSize.width / 2,  1 * childSize.height / 2);
			case LowerLeft:  return center + vector_type( 1 * childSize.width / 2, -1 * childSize.height / 2);
			case LowerRight: return center + vector_type(-1 * childSize.width / 2, -1 * childSize.height / 2);
			default: BOOSTEXT_THROW(boostext::invalid_value_exception(type));
			}
		}

		/**
		 * @return the size of one quadrant at the given depth, using the given rectangle as the root rectangle
		 */
		static size_type size(rect_type rect, std::size_t depth)
		{
			return size_type(rect.width() / pow2(depth),
				rect.height() / pow2(depth));
		}

		/**
		 * @return the result of 2^depth, tweaked to outperform std::pow when 0 <= depth <= 12
		 */
		static std::size_t pow2(std::size_t depth)
		{
			switch(depth)
			{
			case 0: return 1;
			case 1: return 2;
			case 2: return 4;
			case 3: return 8;
			case 4: return 16;
			case 5: return 32;
			case 6: return 64;
			case 7: return 128;
			case 8: return 256;
			case 9: return 512;
			case 10: return 1024;
			case 11: return 2048;
			case 12: return 4096;
			default: return math::pow(2, depth);
			}
		}
	};
	///////////////////////////////////////////////////////////////////////////////////////////////


}
///////////////////////////////////////////////////////////////////////////////////////////////////
